
// 暴力回溯 + 记忆
func wordBreak(s string, wordDict []string) bool {
    /*
        力扣 139 
        1. 确定参数 
            函数返回值是 bool 应该返回 bool值
            入参：开始位置、字符串、单词哈希字典

        2. 确定中止条件
            当开始位置为字符串长度时，结束，返回true

        3. 确定单层递归逻辑
    */
    wordHashMap := map[string]bool{}
    for i:=0; i<len(wordDict); i++ {
        wordHashMap[wordDict[i]] = true
    }
    memoryMap := map[int]bool{}
    return backTracking(s, 0, wordHashMap, memoryMap)
}

func backTracking(s string, start int, wordHashMap map[string]bool, memoryMap map[int]bool) bool {
    if start == len(s) {
        return true
    }
    if v, ok := memoryMap[start]; ok {
        if v == false { return false }    
    }
    for i:=start; i<len(s); i++{
        subS := s[start:i+1]
        if wordHashMap[subS] == true && backTracking(s, i+1, wordHashMap, memoryMap){
            return true
        }
    }
    memoryMap[start] = false
    return false
}

func wordBreak(s string, wordDict []string) bool {
    /*
        力扣 139 动态规划解法
        1. dp[j] 表示 s的第0-j的字串能否由单词组成的结果

        2. dp表达式
            dp[j] = wordHashMap[s[i:j]] && dp[i]

        3. 初始化
            dp[0] = true 无意义， 用于递归

        4. 遍历顺序
            排列、组合都可，且物品数量不限，为完全背包问题 
            先遍历背包或者物品都可以，但是本题求子串，不需要遍历所有的物品，所以先遍历背包

        5. 递推dp数组
    */
    wordHashMap := map[string]bool{}
    for i:=0; i<len(wordDict); i++ {
        wordHashMap[wordDict[i]] = true
    }

    dp := make([]bool, len(s)+1)
    dp[0] = true
    for j:=1; j<=len(s); j++ {
        for i:=0; i<j; i++ {
            if dp[i] && wordHashMap[s[i:j]] {
                dp[j] = true
            }
        }
    }
    fmt.Println(dp)
    return dp[len(s)]
}
